package java学习.代码随想录.动态规划.背包;

/**
 * **************
 * 项目名称: 蓝桥杯-Java学习 <br/>
 * 文件名称:  <br/>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br/>
 * 文件创建：刘世锦Lenovo <br/>
 * 创建时间: 2022/8/15 <br/>
 *
 * @version v1.0 <br/>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br/>
 * *************
 */
public class 目标和 {
    /**
     * 给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。
     * 现在你有两个符号 + 和 -。对于数组中的任意一个整数，
     * 你都可以从 + 或 -中选择一个符号添加在前面。
     *
     * 返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
     *
     * 示例：
     *
     * 输入：nums: [1, 1, 1, 1, 1], S: 3
     * 输出：5
     *
     * 解释：
     * -1+1+1+1+1 = 3
     * +1-1+1+1+1 = 3
     * +1+1-1+1+1 = 3
     * +1+1+1-1+1 = 3
     * +1+1+1+1-1 = 3
     *
     * 一共有5种方法让最终目标和为3。
     *  正-负=sum
     *  正+负=S
     *  2 正 = sum+S
     * 即：最终结果为S，放入正数符号的最大个数
     */

    /**
     * 现已知 正+负=S，而 正-负=sum
     * bagsize =  , 01
     * w nums,
     * v nums[] -nums[]
     * dp[j] 容量为S 能构成的最大次数
     *
     * 将负号放到外面
     * z - f = S
     * z + f = sum  2z = S+sum
     *
     * 正常思维
     * z - f = sum
     * z + f = S   2f = sum-S
     */
    public static int findTargetSumWaysP(int[] nums, int target) {
        int n = nums.length;
        int sum = 0;
        for (int num : nums) {
            sum+=num;
        }
        int plus = target+sum;

        // 因为要是 正整数
        if ((plus)%2!=0 || plus <0){
            return  0;
        }
        int bagsize = (plus)/2;

        int[] dp = new int[bagsize+1];
        dp[0] = 1;

        for (int i = 0; i < n; i++) {
//            i 依旧从0开始0 ： 因为 dp[j] 需要dp【0】
            for (int j = bagsize; j >=nums[i] ; j--) {
                dp[j] += dp[j-nums[i]];

            }
        }
        return dp[bagsize];
    }
    public static int findTargetSumWaysN(int[] nums, int target) {
        int n = nums.length;
        int sum = 0;
        for (int num : nums) {
            sum+=num;
        }
        int negative = sum-target;
        if ((negative)%2!=0 || negative<0){
            return  0; // 因为要是 负整数
        }
        int bagsize = negative/2;
//        if(bagsize<0) bagsize = -bagsize;
        int[] dp = new int[bagsize+1];
        dp[0] = 1;

        for (int i = 0; i < n; i++) {
//            i 依旧从0开始0 ： 因为 dp[j] 需要dp【0】
            for (int j = bagsize; j >=nums[i] ; j--) {
                dp[j] += dp[j-nums[i]];

            }
        }
        return dp[bagsize];
    }


    class Solution {
//        OfficialAnswer
        public int findTargetSumWays(int[] nums, int target) {
            int sum = 0;
            for (int num : nums) {
                sum += num;
            }
            int diff = sum - target;
            if (diff < 0 || diff % 2 != 0) {
                return 0;
            }
            int neg = diff / 2;
            int[] dp = new int[neg + 1];
            dp[0] = 1;
            for (int num : nums) {
                for (int j = neg; j >= num; j--) {
                    dp[j] += dp[j - num];
                }
            }
            return dp[neg];
        }
    }


}
